package com.leetcode.partition5;

import java.util.HashSet;
import java.util.Set;

public class LC419甲板上的战舰 {

    private static final int[][] dirs = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };

    public static void main(String[] args) {
        char[][] board = {
                { 'X', '.', '.', 'X' },
                { '.', '.', '.', 'X' },
                { '.', '.', '.', 'X' }
        };
        System.out.println(countBattleships(board));
    }

    public static int countBattleships(char[][] board) {
        int n = board.length, m = board[0].length;
        UnionFind uf = new UnionFind(n * m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == '.') continue;
                for (int[] dir : dirs) {
                    int x = i + dir[0], y = j + dir[1];
                    if (x < 0 || y < 0 || x >= n || y >= m || board[x][y] == '.') continue;
                    int cur = i * m + j, near = x * m + y;
                    uf.union(near, cur);
                }
            }
        }
        // 检查有多少个连通分量
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'X') {
                    set.add(uf.find(i * m + j));
                }
            }
        }
        return set.size();
    }

    private static class UnionFind {
        private int[] ancestors;

        public UnionFind(int n) {
            ancestors = new int[n];
            for (int i = 0; i < n; i++) ancestors[i] = i;
        }

        public int find(int x) {
            if (ancestors[x] == x) return x;
            return ancestors[x] = find(ancestors[x]);
        }

        public void union(int x, int y) {
            int a = find(x), b = find(y);
            if (a != b) ancestors[b] = a;
        }
    }
}
